package class4;

/**
 * https://leetcode.cn/problems/reverse-bits/description/?envType=problem-list-v2
 * 颠倒二进制位
 */
public class Code11_reverseBits {
    public static void main(String[] args) {
        int n = 10;
        int i = reverseBits(n);
        System.out.println("i = " + i);
    }

    public static int reverseBits(int n) {
        /**
         *
         * 原字符:   a b c d e f g h   ->    h g f e d c b a
         *
         * 操作1:   a b c d e f g h          a b c d e f g h
         * ----------------------------------
         * 右移->:  0 a 0 c 0 e 0 g   =  &   1 0 1 0 1 0 1 0   (0xaaaaaaaa) >>> 1
         * 左移->:  b 0 d 0 f 0 h 0   =  &   0 1 0 1 0 1 0 1   (0x55555555) << 1
         *     |:  b a d c f e h g
         *
         * 操作2:   b a d c f e h g
         * ----------------------------------
         * 右移->:  0 0 b a 0 0 f e   =  &   1 1 0 0 1 1 0 0   (0xcccccccc) >>> 2
         * 左移->:  d c 0 0 h g 0 0   =  &   0 0 1 1 0 0 1 1   (0x33333333) << 2
         *     |:  d c b a h g f e
         *
         * 操作3:   d c b a h g f e
         * ----------------------------------
         * 右移->:  0 0 0 0 d c b a   =  &   1 1 1 1 0 0 0 0   (0xf0f0f0f0) >>> 4
         * 左移->:  h g f e 0 0 0 0   =  &   0 0 0 0 1 1 1 1   (0x0f0f0f0f) << 4
         *     |:  h g f e d c b a
         */
        n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
        n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
        n = (n >>> 16) | (n << 16);
        return n;
    }
}

